#define _CRT_SECURE_NO_WARNINGS 1
class Solution
{
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        srand(time(nullptr));
        return _MergeSort(nums, 0, nums.size() - 1, k);
    }
    int GetRef(vector<int>& nums, int begin, int end)
    {
        return nums[begin + rand() % (end - begin + 1)];
    }
    int _MergeSort(vector<int>& nums, int begin, int end, int k)
    {
        int ref = GetRef(nums, begin, end);
        int left = begin - 1, right = end + 1;
        for (int i = begin; i < right; )
        {
            if (nums[i] < ref) swap(nums[i++], nums[++left]);
            else if (nums[i] > ref) swap(nums[i], nums[--right]);
            else i++;
        }
        int c = end - right + 1;
        int b = right - 1 - (left + 1) + 1;
        if (c >= k) return _MergeSort(nums, right, end, k);
        else if (b + c >= k) return ref;
        else return _MergeSort(nums, begin, left, k - b - c);
    }
};

class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        heights.push_back(0);
        heights.insert(heights.begin(), 0);

        stack<int> st;
        st.push(0);
        int ret = 0;
        for (int i = 1; i < heights.size(); )
        {
            if (heights[i] >= heights[st.top()]) st.push(i), i++;
            else
            {
                int mid = st.top();
                st.pop();
                ret = max(ret, heights[mid] * (i - st.top() - 1));
            }
        }
        return ret;
    }
};
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        int m = nums1.size();
        int n = nums2.size();
        if (n < m)
        {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = 0, right = m;
        while (left <= right)
        {
            int i = left + (right - left) / 2;
            int j = (m + n + 1) / 2 - i;
            if (i != 0 && j != n && nums1[i - 1] > nums2[j]) right = i - 1;
            else if (i != m && j != 0 && nums1[i] < nums2[j - 1]) left = i + 1;
            else
            {
                int maxLeft = 0;
                if (i == 0) maxLeft = nums2[j - 1];
                else if (j == 0) maxLeft = nums1[i - 1];
                else
                {
                    maxLeft = max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) return maxLeft;
                int minRight = 0;
                if (i == m) minRight = nums2[j];
                else if (j == n) minRight = nums1[i];
                else minRight = min(nums1[i], nums2[j]);

                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0;
    }
};
